This invention relates to signal constellations for communication systems.
In communication systems using modems, for example, data is sent over a noise-affected channel by modulating a carrier in accordance with a series of signal points drawn from a constellation of available signal points. In a quadrature amplitude modulation (QAM) system, the constellation is two-dimensional. It is known that certain advantages can be achieved using higher-dimensional constellations to define the points to be transmitted.
An N-dimensional (N greater than 2) constellation C is a finite set of N-tuples (i.e. points each having N coordinates that together define a location in N-space). The principal characteristics of such a constellation are the number .vertline.C.vertline. of its points, the minimum squared distance d.sub.min.sup.2 (C) between its points, and its average energy (or average Euclidean norm) P(C). For a given number of points, the figure of merit of a constellation when used for signaling is P(C)/d.sub.min.sup.2 (C) (the smaller, the better).
A general known method of constructing a good constellation (one with a small figure of merit) having a desired number of points is to choose a finite set of points from a so-called dense (tightly packed) N-dimensional lattice .LAMBDA., or from a coset of .LAMBDA. (i.e., a translated version of .LAMBDA.). The points may be selected by defining a region R in N-space that is just large enough to contain the desired number of points. The minimum squared distance d.sub.min.sup.2 (C) of the constellation is the minimum squared distance d.sub.min.sup.2 (.LAMBDA.) of the lattice .LAMBDA.; in general, to minimize the average energy P(C), the region R should resemble as nearly as possible an N-sphere centered on the origin.
Conway and Sloane, "A Fast Encoding Method for Lattice Codes and Quantizers," IEEE Trans. Inform. Theory, Vol. IT-29, pp. 820-824, 1983, incorporated herein by reference, propose the following way to define such a region R containing the desired number of points. Suppose that a given N-dimensional lattice .LAMBDA. has as a sublattice a scaled version M.LAMBDA. of the same lattice, where M is an integer scaling factor. That is, the sublattice is a subset of the points of the lattice selected so that the sublattice will be simply a larger scale version of the lattice. (Note that M.LAMBDA. and .LAMBDA. are lattices of the same type.) Then there are M.sup.N equivalence classes of points in the original lattice .LAMBDA. (or any coset of .LAMBDA.) module M.LAMBDA.. Note that two N-tuples are equivalent modulo M.LAMBDA. (and hence belong to an equivalence class) if their difference is a point in M.LAMBDA..
The so-called Voronoi region of the lattice M.LAMBDA. is the set of points in N-space that are at least as close to the origin as to any other lattice point in M.LAMBDA.. The interior of the Voronoi region may be defined as the set of points closer to the origin than to any other lattice point; the boundary of the Voronoi region is the set of points for which the origin is one of the closest points in the lattice, but for which there are other equally near lattice points. In general, the boundary is a closed surface in N-space, composed of a certain number of (N-1)-dimensional faces, which are portions of hyperplanes equidistant between two neighboring lattice points in M.LAMBDA.. (For example, the Voronoi region of an N-dimensional integer lattice Z.sup.N is an N-cube of side 1, whose faces are (N-1)-cubes of side 1. The intersections of the faces are figures of N-2 or fewer dimensions and have more than two nearest neighbors.)
Therefore, if .LAMBDA.+c is a coset of the original lattice (where c is the translation vector) that is chosen to have no points on the boundary of the Voronoi region of the scaled lattice M.LAMBDA., then the Voronoi region contains M.sup.N points of the coset .LAMBDA.+c, one from each equivalence class modula M.LAMBDA., and the M.sup.N point Voronoi region may serve as a signal constellation called a Voronoi constellation (Conway and Sloane call it a Voronoi code). Such constellations are characterized by relatively small average energy and are subject to relatively simple implementation.